%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Block Ciphers}
\label{BlockCiphers}

\begin{center}{\large\bf Data Encryption Standard}\end{center}

The Data Encryption Standard, or DES, is one of the most important
examples of a Feistel cryptosystem.  DES was the result of a contest
set by the U.S. National Bureau of Standards (now called the NIST)
in 1973, and adopted as a standard for unclassified applications
in 1977.

The winning standard was developed at IBM, as a modification of the
previous system called LUCIFER.  The DES is widely used for encryption
of PIN numbers, bank transactions, and the like.  DES is also specified
as an Australian banking standard.

The DES is an example of a Feistel cipher, which operates on blocks
of 64 bits at a time, with an input key of 64 bits.  Every 8th bit in
the input key is a parity check bit which means that in fact the key
size is effectively reduced to 56 bits.

\begin{center}
{\large\bf Advanced Encryption Standard}
\end{center}

In 1997, the NIST called for submissions for a new standard to replace
the aging DES.  The contest terminated in November 2000 with the selection
of the Rijndael cryptosystem as the Advanced Encryption Standard (AES).

\section{Product ciphers and Feistel ciphers}

As a precursor to the description of DES, we make the following
definitions, which describe various aspects of the constructions,
specific properties, and design components of DES.

A {\em product cipher} is a composite of two or more elementary
ciphers with the goal of producing a cipher which is more secure
that any of the individual components.
A {\em substitution-permutation network} is a product cipher
composed of stages, each involving substitutions and permutations,
in which the blocks can be partitioned into smaller blocks for
substitutions and recombined with permutations.  An {\em iterated
block cipher} is a block cipher involving the repetition of an
internal {\em round function}, which may involve a key as input.
Each of the sequential steps is termed a {\em round}.

We now describe in more detail an example of an iterated block
cipher, called a {\em Feistel cipher}.  In a Feistel cipher the input block
is of even length $2t$, of the form $L_0R_0$, and outputs ciphertext
of the form $R_rL_r$.  For each $i$ such that $1 \le i \le r$, the
round map takes $L_{i-1}R_{i-1}$ to $L_iR_i$, where $L_i = R_{i-1}$
and $R_i = L_{i-1}\oplus f_{K_i}(R_{i-1})$, where $f_{K_i}$ is a cipher
which depends only on an input subkey $K_i$, which is derived from
the cipher key $K$.

The flow of the Feistel cipher therefore looks something like:
$$
\SelectTips{cm}{10}
\xymatrix@R=4mm@C=2mm{
\fbox{\quad\hbox{$L_{i-1}$}\quad} \ar@{-}[rd] &
\fbox{\quad\hbox{$R_{i-1}$}\quad} \ar@{-}[d]^{f_{K_{i}}}
                                  \ar@{->}[ldd] \\
& \oplus \ar@{->}[d] \\
\fbox{\quad\hbox{\ $L_{i}$\ }\quad} &
\fbox{\quad\hbox{\ $R_{i}$\ }\quad}
}
$$
We can eliminate the $L_i$ by defining $R_{-1} = L_0$, so
that the input is $R_{-1}R_0$, and the round operations are
of the form $R_i = R_{i-2}\oplus f_{K_i}(R_{i-1})$, in which
case the flow diagram looks like:
$$
\SelectTips{cm}{10}
\xymatrix@R=4mm@C=2mm{
\mbox{\hspace{8mm}}
    \ar@/^{24mm}/[ddd] \\ \\
\fbox{\quad\hbox{$R_{i-2}$}\quad}
    \ar@{-}[d]^(0.6){f_{K_{i-1}}}
    \ar@/^{24mm}/[ddd] \\
\oplus \ar@{->}[d] \\
\fbox{\quad\hbox{$R_{i-1}$}\quad}
    \ar@{-}[d]^(0.6){f_{K_{i}}} \\
\oplus \ar@{->}[d] \\
\fbox{\quad\hbox{\ $R_{i}$\ }\quad}
}
$$
The final output of the Feistel cipher is the inverted pair
$R_rL_r = R_rR_{r-1}$, which allows the Feistel cipher to be
inverted by running through the same algorithm with the key
sequence reversed.

We now prove that reversing the internal key sequence gives the
inverse cipher, by a comparison of the enciphering and deciphering
sequences $\{R_i\}$ and $\{R'_j\}$.

\noindent{\bf Enciphering.}
A message $M = L_0R_0 = R_{-1}R_0$, is enciphered via the
iteration:
\begin{equation}
\label{FeistelEnciphering}
R_{i+1} = R_{i-1} \oplus f_{K_{i+1}}(R_i),
\end{equation}
with respect to a key sequence $K_1,K_2,\dots,K_r$.

\noindent{\bf Deciphering.}
Suppose we begin with $C = R_rR_{r-1} = R'_{-1}R'_0$, and a
reversed key sequence $K'_1,K'_2\dots,K'_r = K_r,K_{r-1}\dots,K_1$.
The deciphering follows the same algorithm as enciphering with
respect to this key sequence:
\begin{equation}
\label{FeistelDeciphering}
R'_{j+1} = R'_{j-1} \oplus f_{K'_{j+1}}(R'_j).
\end{equation}
Setting $j = r-i-1$, we have $K'_{j+1} = K'_{r-i} = K_{i+1}$.
We moreover want to show the relations
$$
R'_{-1} = R_r,\ R'_0 = R_{r-1}, \dots, R'_{r-1} = R_0,\ R'_r = R_{-1}.
$$
In other words, we want to show that $R'_j = R_i$ whenever $i+j=r-1$.

Clearly this relation holds for $(i,j) = (r,-1)$ and $(i,j) = (r-1,0)$.
Assuming it holds for $j-1$ and $j$ we prove that it holds for $j+1$.
The deciphering sequence~\eqref{FeistelDeciphering} can be replaced by
$$
R'_{j+1} = R'_{j-1} \oplus f_{K'_{j+1}}(R'_j)
         = R'_{r-i-2} \oplus f_{K'_{r-i}}(R'_{r-i-1})
         = R_{i+1} \oplus f_{K_{i+1}}(R_i)
$$
The expression $R_{i+1} = R_{i-1} \oplus f_{K_{i+1}}(R_i)$
in~\eqref{FeistelDeciphering} can be rearranged by adding (= subtracting)
$f_{K_{i+1}}(R_i)$ to both sides to get
$R_{i+1} \oplus f_{K_{i+1}}(R_i) = R_{i-1}$.
We conclude that $R'_{j+1} = R_{i-1}$, so the equality holds by
induction.

%\begin{center}{\Large\bf MATH3024: Lecture 10}\end{center}

\begin{example}[Feistel cipher]

Let $f_{K_i}$ be the block cipher, of block length 4, which is the
composition of the following maps:
\begin{enumerate}
\item
The transposition cipher $T = [4,2,1,3]$; followed by
\item
A bit-sum with the 4-bit key $K_i$; followed by
\item
A substitution cipher $S$ applied to the 2-bit blocks
$$
S(00) = 10,\quad S(10) = 01,\quad S(01) = 11,\quad S(11) = 00,
$$
i.e. $b_1b_2b_3b_4 \mapsto S(b_1b_2)S(b_3b_4)$.
\end{enumerate}

Let $C$ be the 3-round Feistel cryptosystem of key length 12, where
the three internal keys $K_1$, $K_2$, $K_3$ are the first, second, and
third parts of the input key $K$, and the round function is $f_{K_i}$.

\noindent{\bf Exercise.}
Compute the enciphering of the text $M = 11010100$, using the
key $K =001011110011$.
\end{example}

\section{Digital Encryption Standard Overview}

The DES is a 16-round Feistel cipher, which is preceded and followed
by an initial permutation $IP$ and its inverse $IP^{-1}$.  That is, we
start with a message $M$, and take $L_0R_0 = IP(M)$ as input to the
Feistel cipher, with output $IP^{-1}(R_{16}L_{16})$.  The 64-bits of
the key are used to generate $16$ internal keys, each of $48$ bits.
The steps of the round function $f_K$ is given by the following sequence,
taking on 32-bit strings, expanding them to 48-bit strings, and applying
a 48-bit block function.
\begin{enumerate}
\item
Apply a fixed {\em expansion permutation} $E$ --- this function
is a permutation the 32 bits with repetitions to generate a 48-bit block
$E(R_i)$.
\item
Compute the bit-sum of $E(R_i)$ with the 48-bit key $K_i$, and write
this as 8 blocks $B_1,\dots,B_8$ of 6 bits each.
\item
Apply to each block $B_j = b_1b_2b_3b_4b_5b_6$ a substitution $S_j$.
These substitutions are specified by {\em $S$-boxes}, which describe
the substitution as a look-up table.  The output of the substitution
cipher is a 4-bit string $C_j$, which results in the 32-bit string
$C_1C_2C_3C_4C_5C_6C_7C_8$.
\item
Apply a fixed 32-bit permutation $P$ to $C_1C_2C_3C_4C_5C_6C_7C_8$,
and output the result as $f_{K_i}(R)$.
\end{enumerate}
This completes the description of the round function $f_{K_i}$.

%\begin{center}{\Large\bf MATH3024: Lecture 12}\end{center}

\section{Advanced Encryption Standard Overview}

In 1997, the NIST called for submissions for a new standard to replace
the aging DES.  The contest terminated in November 2000 with the selection
of the Rijndael cryptosystem as the Advanced Encryption Standard (AES).

The Rijndael cryptosystem operates on 128-bit blocks, arranged as
$4\times 4$ matrices with 8-bit entries.  The algorithm consists of
multiple iterations of a round cipher, each of which is the composition
of the following four basic steps:
\begin{itemize}
\item
{\em ByteSub} transformation.  This step is a nonlinear substitution,
given by a $S$-box (look-up table), designed to resist linear and
differential cryptanalysis.
\item
{\em ShiftRow} transformation.  Provides a linear mixing for diffusion
of plaintext bits.
\item
{\em MixColumn} transformation.  Provides a similar mixing as in the
ShiftRow step.
\item
{\em AddRoundKey} transformation.  Bit-wise {\tt XOR} with the round key.
\end{itemize}
The Advanced Encryption Standard allows Rijndael with key lengths 128,
192, or 256 bits.

The eight-bit byte blocks which form the matrix entries are interpreted
as elements of the finite field of $2^8 = 256$ elements.  The finite field
is represented by the quotient ring
$$
\F_{2^8} = \F_2[X]/(X^8+X^4+X^3+X+1),
$$
whose elements are polynomials
$c_7X^7 + c_6X^6 + c_5X^5 + c_4X^4 + c_3X^3 + c_2X^2 + c_1X + c_0$.

We denote by BS, SR, MC, and ARK these four basic steps.  There exist
corresponding inverse operations IBS, ISR, IMC, IARK.  The flow of the
algorithms for enciphering and deciphering are as follows:
\begin{center}
\begin{minipage}[t]{48mm}
\begin{enumerate}
%\setcounter{enumerate}{0}
\item
ARK
\item
BS, SR, MC, ARK
$$\vdots$$
%\setcounter{enumerate}{9}
\item
BS, SR, MC, ARK
\item
BS, SR, ARK
\end{enumerate}
\end{minipage}
\begin{minipage}[t]{50mm}
\begin{enumerate}
%\setcounter{enumerate}{0}
\item
ARK
\item
IBS, ISR, IMC, IARK
$$\vdots$$
%\setcounter{enumerate}{9}
\item
IBS, ISR, IMC, IARK
\item
IBS, ISR, ARK
\end{enumerate}
\end{minipage}
\end{center}

\noindent{\bf ByteSub.}
The ByteSub operation is given by the $S$-box look-up table.
%$$
%\begin{array}{cccccccccccccccc}
%{\text{Work out the description of an $S$-box.}}
%\end{array}
%$$
Alternatively the $S$-box has a description in terms of the structure
of the finite fields and linear algebra.  Let $x'$ be the inverse of
$x$ in $\F_{2^8}$ if $x \ne 0$ and set $x' = x = 0$ otherwise.
Then the ByteSub step is given by $x \mapsto X^6+X^5+X+1+x'A$ where
$A$ is the matrix:
$$
A =
\left(
\begin{array}{cccccccc}
1&1&1&1&1&0&0&0\\
0&1&1&1&1&1&0&0\\
0&0&1&1&1&1&1&0\\
0&0&0&1&1&1&1&1\\
1&0&0&0&1&1&1&1\\
1&1&0&0&0&1&1&1\\
1&1&1&0&0&0&1&1\\
1&1&1&1&0&0&0&1
\end{array}
\right)
$$

%\begin{center}{\Large\bf MATH3024: Lecture 11}\end{center}

\section{Modes of Operation}

Block ciphers can be applied to longer ciphertexts using one of
various {\it modes of operation}.  We assume that the input is
plaintext $M = M_1M_2\ldots$, the block enciphering map for given
key $K$ is $E_K$, and the output is $C = C_1C_2\ldots$.
The possible block cipher {\em modes of operation} which we treat
are identified by the acronyms ECB, CBC, CFB, and OFB.   In each
case we assume that we have a cipher of block length $n$, with
enciphering maps $E_K$ and deciphering maps $D_K$ for each key $K$.

\subsection{Electronic Codebook Mode (ECB)}

Electronic codebook mode is the most obvious way to use a block cipher.

\noindent
{\bf Enciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit plaintext blocks $M = M_1M_2\dots M_t$.

\noindent
{\bf Algorithm:}
$$
C_j = E_K(M_j).
$$

\noindent
{\bf Output:}\\
$n$-bit ciphertext blocks $C = C_1 C_2\dots C_t$.

\noindent
{\bf Deciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit ciphertext blocks $C = C_1 C_2\dots C_t$.

\noindent
{\bf Algorithm:}
$$
M_j = D_K(C_j).
$$

\noindent
{\bf Output:}\\
$n$-bit plaintext blocks $M = M_1 M_2\dots M_t$.

To explain the name, one should think of this mode as being
defined by a lookup table or {\em codebook}.  Consider, for
example, DES, which operates on 64 bit (binary) strings.
These describe, for instance, 8 characters in 8-bit ASCII
(or in 7-bit ASCII with one parity check bit).  For each
key $K$, the codebook contains the ciphertext image of each
of these 8 character strings as a lookup table.  In order
to encipher the message, the electronic codebook is consulted
for the ciphertext encoding of each block.  Note that the
number of such hypothetical codebooks is itself enormous --
for DES there are $2^{56}$ possible keys, each with its own
codebook.

We now consider some of the properties and limitations of
ECB mode.  The categories below are chosen for comparison
with the modes of operations which follow.

\noindent
{\bf Properties:}\\
\noindent
{\bf 1. Identical plaintext.} The same plaintext block always maps
to the same ciphertext block. \\
{\bf 2. Chaining dependencies.} Reordering the plaintext blocks
induces a reordering of the same ciphertext blocks. \\
{\bf 3. Error propagation.} An error in a ciphertext block results
in a deciphering error only in the corresponding plaintext block.

\noindent
{\bf Security Remarks:}\\
1. Malicious substitution of a ciphertext block $C_j$ results in
substitution of message block $M_j$. \\
2. Blocks $C_j$ do not hide patterns -- the same block $M_j$ is
enciphered in the same way.

\noindent
{\bf Conclusion.}
Although commonly used, electronic codebook mode is not recommended
for use if $t>1$ with the same key.  Security can be improved by
inclusion of random padding bits in each block.


\subsection{Cipher Block Chaining Mode (CBC)}

Cipher block chaining mode involves a vector bit sum operation
of the message block with the previous ciphertext block prior
to enciphering.  The ciphertext blocks are initialized with a
randomly chosen message which may be transmitted openly, i.e.
the security of the cryptosystem is based on the secrecy of the
key, not on the secrecy of initialization vector.

\noindent
{\bf Enciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit initialization vector $C_0$ \\
$n$-bit plaintext blocks $M = M_1 M_2\dots M_t$.

\noindent
{\bf Algorithm:}
$$
C_j = E_K(C_{j-1} \oplus M_j).
$$

\noindent
{\bf Output:}\\
$n$-bit ciphertext blocks $C = C_0 C_1\dots C_t$.

\noindent
{\bf Deciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit ciphertext blocks $C = C_0 C_1\dots C_t$.

\noindent
{\bf Algorithm:}
$$
M_j = C_{j-1} \oplus D_K(C_j).
$$

\noindent
{\bf Output:}\\
$n$-bit plaintext blocks $M = M_1 M_2\dots M_t$.

\noindent
{\bf Properties:}\\
\noindent
{\bf 1. Identical plaintext.} The same sequence of ciphertext blocks
result when the same key and the same initialization vector are used.\\
{\bf 2. Chaining dependencies.} The chaining mechanism causes $C_j$
to depend on $C_{j-1}$ and $M_j$, so enciphering is not independent
of reordering. \\
{\bf 3. Error propagation.} An error in a ciphertext block $C_j$
affects decipherment of $C_j$ and $C_{j+1}$.  For a reasonable
enciphering algorithm, a single bit error affects $50\%$ of the
bits in the deciphered plaintext block $M_j'$, while the bit error
affects only that bit of $M_{j+1}'$. \\
{\bf 3. Error recovery.} The cryptosystem is said to be
self-recovering, in the sense that while an error in $C_j$ results
in incorrectly deciphered plaintext $M_j'$ and $M_{j+1}'$, the
ciphertext $C_{j+2}$ correctly deciphers to $M_{j+2}' = M_{j+2}$.

\subsection{Cipher Feedback Mode (CFB)}

Cipher feedback mode allows one to process blocks of size $r < n$
at a time.  The typical value for $r$ is $1$, while $n$ may be of
size $64$, using DES.

\noindent
{\bf Enciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit initialization vector $I_1$ \\
$r$-bit plaintext blocks $M = M_1 M_2\dots M_t$.

\noindent
{\bf Algorithm:}
$$
\begin{array}{ll}
C_j = M_j \oplus L_r(E_K(I_j)), \\
I_{j+1} = R_{n-r}(I_j)\,||\,C_j,
\end{array}
$$
where $L_r$ and $R_{n-r}$ are the operators which take the
left-most $r$-bits and the right-most $n-r$-bits, and $||$ is
the concatenation operator.

The vector $I_j$ should be thought of as a {\em shift register},
a block of $n$-bits of memory which stores some state of the
algorithm.  The formation of $I_{j+1}$ is a left-shift by $r$ of
this block, discarding the left-most $r$ bits, with the right-most
$r$ bits replaced by $C_j$.

\noindent
{\bf Deciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit initialization vector $I_1$ \\
$r$-bit ciphertext blocks $C = C_1 C_2\dots C_t$.

\noindent
{\bf Algorithm:}\\
Compute $I_1,\dots,I_t$ as in the enciphering algorithm, which
can be generated independently of the deciphered message text,
and then compute
$$
M_j = C_j \oplus L_r(E_K(I_j)).
$$

Note that CFB deciphering requires only the block cipher $E_K$,
not the inverse block deciphering map $D_K$.

\noindent
{\bf Properties:}\\
\noindent
{\bf 1. Identical plaintext.} The same sequence of ciphertext blocks
results when the same key and initialization vector is used.  Changing
the initialization vector changes the ciphertext.\\
{\bf 2. Chaining dependencies.} Ciphertext block $C_j$ depends on
the previous plaintext blocks $M_{j-1},\dots, M_1$ as well as $M_j$,
so the ciphertext blocks are not reordering independent.\\
{\bf 3. Error propagation.} An error in $C_j$ affects the
decipherment of the next $[n/r]$ plaintext blocks.  The recovered
plaintext $M_j'$ will differ from $M_j$ at exactly the bits for
which $C_j$ was in error.  These bit errors will appear in
subsequent blocks $M_{j+k}'$ at translated positions.\\
{\bf 4. Error recovery.} Proper deciphering requires the shift
register to be correct, for which the previous $[n/r]$ ciphertext
blocks are required.  The decipherment is self-recovering from
errors, but only after $[n/r]$ blocks (approximately the same
$n$-bits of the ciphertext block in error).\\
{\bf 5. Throughput.} The rate of enciphering and deciphering is
reduced by a factor of $n/r$, that is, for every $r$ bits of
output the algorithm must carry out one $n$-bit enciphering
operation.

\subsection{Output Feedback Mode (OFB)}

Output feedback mode has a similar use as cipher feedback mode, but
is relevant to applications for which error propagation must be
avoided.  Output feedback mode is an example of a {\em synchronous
stream cipher} (constructed from a block cipher), in which the
keystream is created independently of the plaintext stream.

\noindent
{\bf Enciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit initialization vector $I_0$ \\
$r$-bit plaintext blocks $M = M_1 M_2\dots M_t$.

\noindent
{\bf Algorithm:}
$$
\begin{array}{l}
I_j = E_K(I_{j-1})\\
C_j = M_j \oplus L_r(I_j)
\end{array}
$$

\noindent
{\bf Deciphering.}

\noindent
{\bf Input:}\\
$k$-bit key $K$ \\
$n$-bit initialization vector $I_0$ \\
$r$-bit ciphertext blocks $C = C_1 C_2\dots C_t$.

\noindent
{\bf Algorithm:}\\
Compute $I_1,\dots,I_t$ as in the enciphering algorithm.
$$
M_j = C_j \oplus L_r(I_j)
$$


\noindent
{\bf Properties:}\\
\noindent
{\bf 1. Identical plaintext.}  The same comments for CBC and CFB apply.\\
{\bf 2. Chaining dependencies.}  The ciphertext output is order dependent,
but the keystream $I_1,I_2,\dots$ is plaintext independent.\\
{\bf 3. Error propagation.} An error in a ciphertext bit affects only
that bit of the plaintext.\\
{\bf 4. Error recovery.}  The cipher is self-synchronizing, and bit errors
in a ciphertext block affect only that bit of the recovered plaintext.
It recovers immediately from bit errors, but bit losses affect alignment.\\
{\bf 5. Throughput.} As with CFB, the rate of enciphering and
deciphering is reduced by a factor of $n/r$, however the vectors
$I_j$ can be precomputed from $K$ and $I_0$, independently of the
ciphertext blocks.

\section*{Exercises}

\input{exercises/BlockCiphers}
